package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-01-28 11:40
 */
public class QLint800 {
    public double backpackIX(int m, int[] prices, double[] probability) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        double[][] dp = new double[n + 1][m + 1];
        int[][] pi = new int[n + 1][m + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= m; i++) {
            //-1表示拼不出来m
            dp[0][i] = -1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - prices[i - 1] >= 0
                        && dp[i - 1][j - prices[i - 1]] != -1
                        && dp[i][j] < dp[i - 1][j - prices[i - 1]] + probability[i - 1]) {
                    dp[i][j] = dp[i - 1][j - prices[i - 1]] + probability[i - 1];
                    pi[i][j] = 1;
                }
            }
        }

        double res = 0;
        int max = 0;
        for (int i = 0; i <= m; i++) {
            if (res < dp[n][i]) {
                res = dp[n][i];
                max = i;
            }
        }

        double res2 = 1;
        //进行回溯
        for (int i = n; i >= 1; i--) {
            if (pi[i][max] == 1) {
                res2 *= (1 - probability[i - 1]);
                max -= prices[i - 1];
            }
        }

        return 1 - res2;
    }


    public double backpackIX2(int m, int[] prices, double[] probability) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        double[] dp = new double[m + 1];
        int[][] pi = new int[n + 1][m + 1];
        dp[0] = 0;
        for (int i = 1; i <= m; i++) {
            //-1表示拼不出来m
            dp[i] = -1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 0; j--) {
                if (j - prices[i - 1] >= 0
                        && dp[j - prices[i - 1]] != -1
                        && dp[j] < dp[j - prices[i - 1]] + probability[i - 1]) {
                    dp[j] = dp[j - prices[i - 1]] + probability[i - 1];
                    pi[i][j] = 1;
                }
            }
        }

        double res = 0;
        int max = 0;
        for (int i = 0; i <= m; i++) {
            if (res < dp[i]) {
                res = dp[i];
                max = i;
            }
        }

        double res2 = 1;
        //进行回溯
        for (int i = n; i >= 1; i--) {
            if (pi[i][max] == 1) {
                res2 *= (1 - probability[i - 1]);
                max -= prices[i - 1];
            }
        }

        return 1 - res2;
    }


    public static void main(String[] args) {
        new QLint800().backpackIX(7, new int[]{4, 4, 5}, new double[]{0.1, 0.2, 0.3});
    }
}
